#include <stdlib.h>
#include <stdio.h>

#define X 12

int partition(int* a, int p, int r)
{
	int i = p - 1, j = p;
	while(j < r)
	{
		if(a[j] <= a[r])
		{
			int temp = a[j];
			a[j] = a[i + 1];
			a[i + 1] = temp;
			i++;
		}//end if(a[j] <= a[r])
		j++;
	}//end while

	int temp = a[i + 1];
	a[i + 1] = a[r];
	a[r] = temp;

	return i + 1;
}

int randomized_partition(int *a, int p, int r)
{
	int i = p + rand() % (r - p + 1);

	int temp = a[r];
	a[r] = a[i];
	a[i] = temp;

	partition(a, p, r);
}

int hoare_partition(int *a, int p, int r)
{
	int x = a[p];
	int i = p - 1, j = r + 1;
	while(1)
	{
		do
		{
			j--;
		} while(a[j] > x);

		do
		{
			i++;
		} while(a[i] < x);

		if(i < j)
		{
			int temp = a[i];
			a[i] = a[j];
			a[j] = temp;
		}
		else 
		{
			printf("x: %d, i: %d, j: %d\n", x, i, j);
			return j;
		}
	}
}

void hoare_quickSort(int *a, int p, int r)
{
	if(p < r)
	{
		int q = hoare_partition(a, p, r);
		printf("%d,%d,%d\n", p, q, r);
		sleep(1);
		hoare_quickSort(a, p, q);
		hoare_quickSort(a, q + 1, r);
	}
}

void stoogeSort(int *a, int i, int j)
{
	if(a[i] > a[j])
	{
		int temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}
	
	if(i + 1 >= j)
		return ;

	int k = (j - i + 1) / 3;
	stoogeSort(a, i, j - k);
	stoogeSort(a, i + k, j);
	stoogeSort(a, i, j - k);
}

void quickSort(int* a, int p, int r)
{
	if(p < r)
	{
		int q = partition(a, p, r);
		quickSort(a, p, q - 1);
		quickSort(a, q + 1, r);
	}//end if(p < r)
}

void tailRecursionQuickSort(int *a, int p, int r)
{
	while(p < r)
	{
		int q = partition(a, p, r);
		tailRecursionQuickSort(a, p, q - 1);
		p = q + 1;
	}
}

void randomized_quickSort(int* a, int p, int r)
{
	if(p < r)
	{
		int q = randomized_partition(a, p, r);
		quickSort(a, p, q - 1);
		quickSort(a, q + 1, r);
	}//end if(p < r)
}

void print(int* a, int n)
{
	int i;
	for(i = 0; i < n; i++)
		printf("%d ", a[i]);
	printf("\n********\n");
}

void test()
{
	srand(time(0));
	int data[X] /*= {13, 19, 9, 5, 12, 8, 7, 4, 11, 2, 6, 21, }*/;
	int i;
	for(i = 0; i < X; i++)
	{
		data[i] = rand() % 10000;
	}//end for
	printf("originail: \n");
	print(data, X);

	//hoare_quickSort(data, 0, X - 1);
	tailRecursionQuickSort(data, 0, X - 1);
	for(i = 0; i < X - 1; i++)
	{
		if(data[i] > data[i + 1])
		{
			printf("error\n");
			break;
		}//end if
	}//edn for
	printf("sorted: \n");
	print(data, X);
}

int main()
{
	while(1)
	{
		test();
		sleep(1);
	}//while(1)
}
